
from xml.dom.minidom import parse, parseString
import re


class GraphException:
    def __init__(self, error_msg):
        self.error = error_msg

class GraphNode:
    def __init__(self, value):
        self.value = value
        
    def toXml(self):
        return str(self.value)
        
class Graph:

    def __init__(self):
        self.nodes = {}
        self.edges = []
        self.index = 0
        
    def addNode(self, node):
        if not node in self.nodes:
            self.nodes[self.index] = node
            self.index = self.index + 1
        else:
            raise GraphException("Node already exists")
    
    def removeNode(self, node):
        self.nodes = { key: value for (key, value) in self.nodes.items() if value is not node}
        self.edges = [(node1, node2) for node1, node2 in self.edges if node<>node1 and node<>node2]
    
    def edgeExists(self, edge):
        result = [e for e in self.edges if e[0] == edge[0] and e[1] == edge[1]]
        return len(result) == 1
    
    def addEdge(self, node1, node2):
        if not node1 in self.nodes.values():
            raise GraphException("Node not yet in the graph")
        if not node2 in self.nodes.values():
            raise GraphException("Node not yet in the graph")
        edge = [node1, node2]
        if not edge in self.edges:
            self.edges.append([node1, node2])    
        else:
            raise GraphException("Edge already exists")
            
    def removeEdge(self, edge):
        self.edges = [e for e in self.edges if e[0] <> edge[0] or e[1] <> edge[1]]
        
    def find(self, node):
        return [ x for x in self.nodes.values() if x == node ]
        
    def parents(self, node):
        if not node in self.nodes.values():
            raise GraphException("Node not yet in the graph")
        return [node1 for (node1, node2) in self.edges if node2 == node]    
        
    def children(self, node):
        if not node in self.nodes.values():
            raise GraphException("Node not yet in the graph")
        return [node2 for (node1, node2) in self.edges if node1 == node]  
    
      
    def find_path(self, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        for child in self.children(start):
            if child not in path:
                newpath = self.find_path(child, end, path)
                if newpath: return newpath
        return None
    
    def subgraph(self, dependency):
        stack = [dependency]
        treated = []
        while len(stack) <> 0:
            node = stack[0]
            treated.append(node)
            stack.remove(node)
            
            children = self.children(node) 
            not_treated_children = [child for child in children if not child in treated and not child in stack]
            stack = stack + not_treated_children
        g = Graph()
        print "\n".join([t.name for t in treated])
        for node in treated:
            g.addNode(node)
        for node1 in treated:
            for node2 in treated:
                edge = [node1, node2]
                if self.edgeExists(edge):
                    print node1.name, node2.name
                    g.addEdge(node1, node2)  
        return g
    
    def getNodeFromIndex(self, index):
        return self.nodes[index]
        
            
    def toXml(self):
        xml = ""
        xml = "<graph>\n"
        xml += "\t<nodes>\n"
        for (node, index) in self.nodes:
            xml += "\t\t<node index=\""+str(index)+"\">\n"
            xml += "\t\t\t<value>" + node.toXml() + "</value>\n"
            xml += "\t\t</node>\n"
        xml += "\t</nodes>\n"
        
        xml += "\t<children>\n"
        for (node, index) in self.nodes.items():
            children = [node2 for (node1, node2) in self.edges if node1 == node]
            for child in children:
                the_index = [i for (n, i) in self.nodes.items() if n == child]
                if len(the_index) == 1:
                    xml += "\t\t<child parent=\""+str(index)+"\" child=\""+str(the_index[0])+"\"/>\n"
                elif len(the_index) == 0:
                    raise GraphError("The node is not in the graph yet")
        xml += "\t</children>\n"
        xml += "</graph>\n"  
        return xml
        
    def fromXml(self, str):
        pass
            
            

if __name__=='__main__':
    
    g = Graph()
    node1 = GraphNode("Coucou")
    node2 = GraphNode("Test1")
    node3 = GraphNode("Tst2")
    node4 = GraphNode("Tst2")
    
    g.addNode(node1)
    g.addNode(node2)
    g.addNode(node3)
    #g.addNode(node4)
    
    g.addEdge(node1, node2)
    g.addEdge(node2, node1)
    g.addEdge(node1, node3)
    g.addEdge(node1, node1)
    
    print "Found=", g.find("Tst2")
    
    
    xml =  g.toXml()
    print xml
    
    g1 = Graph()
    g1.fromXml(xml)
    
    #print "New Graph"
    print g1.toXml()